TRIE-GEN

Section: User Commands (1)
Updated: 12 December 1989
Index Return to Main Contents

NAME

trie-gen - generate a minimal-prefix trie

SYNOPSIS

trie-gen [ -c ] < keyfile

DESCRIPTION

TRIE-GEN is a program that reads a user-specified set of keywords from standard input and generates a minimal-prefix trie. Minimal-prefix tries have several useful properties that make them efficient implementations for static search sets. The table-driven trie generated by TRIE-GEN recognizes keywords in the search set in time proportional to the length of the shortest unambiguous prefix for a given keyword.

Consider a command interpreter for an interactive debugger or operating system shell (e.g., gdb or VMS). It is frequently nice to allow users to type the `minimal unambiguous prefix' for any command in the set of built-in keywords. For example, given the following complete list of system commands:

----------------------------------------
bash
bison
diff
diff3
egrep
flex
g++
gawk
gcc
gdb
genclass
gnuchess
gnuplot
gperf
grep
indent
make
sed
----------------------------------------

and assuming these are the only available commands, a user could invoke the egrep program simply by entering a single `e', but would need to enter `ba' to run bash or `gnuc' to run gnuchess.

TRIE-GEN generates several static lookup tables and two functions that allow client programs to either interpret standard input one character at a time or, given a prefix string, to determine which keyword in the static search set this prefix string matches.

The trie generation algorithm runs in time proportional to O(n * k), where n is the number of user-specified keywords from the standard input and k is the length of the longest common prefix between any words in the keyword set.

The table compaction algorithm, invoked by giving the `-c' option, runs in time proportional to O(r * e * 128), where r is the total number of rows in the generated trie, e is the maximum number of non-null entries in each row, and 128 is the size of the ASCII character set used to index into the trie.

OPTIONS

-c: Compact the generated trie using a technique called `double-offset indexing,' which is used in Bison and FLEX (also described in Tarjan and Yao's article ``Storing a Sparse Table'' in CACM, 1979). -f Generates a `full' trie rather than a minimal-prefix trie.

BUGS

None known at this time, though there is much work to be done with the user interface and program options... Bugs should be reported to schmidt@ics.uci.edu. Bugs tend actually to be fixed if they can be isolated, so it is in your interest to report them in such a way that they can be easily reproduced.

COPYING

Copyright (c) 1989 Free Software Foundation, Inc. Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies. Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one. Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be included in translations approved by the Free Software Foundation instead of in the original English.

AUTHORS

Douglas C. Schmidt (schmidt@ics.uci.edu)

This document was created by man2html, using the manual pages.
Time: 17:19:42 GMT, January 16, 2023